# -*- coding: utf-8 -*-

"""931. 下降路径最小和
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

示例 1：
输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：如图所示，为和最小的两条下降路径

示例 2：
输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：如图所示，为和最小的下降路径

提示：
n == matrix.length == matrix[i].length
1 <= n <= 100
-100 <= matrix[i][j] <= 100"""

class Solution:
    """
    定义 f(i, j) 为从首行到达尾行位置 (i,j) 的最小路径和。
    递归基础：
        f(0, x) = matrix[0][x]    # 首行等于点值
    递归定义：
        f(i, j) = min( f(i-1, j-1), f(i-1, j), f(i-1, j+1) ) + matrix[i][j]    # 首行后除了第一个和最后一个位置
        f(i, j) = min( f(i-1, j), f(i-1, j+1) ) + matrix[i][j]                 # 首行后第一个位置
        f(i, j) = min( f(i-1, j-1), f(i-1, j) ) + matrix[i][j]                 # 首行后最后一个位置
    通过动态规划，将递归运算转换为递推的状态迭代。
    """
    def minFallingPathSum(self, matrix: list) -> int:
        n = len(matrix)
        i = 1
        while i < n:
            matrix[i][0] += min(matrix[i-1][0], matrix[i-1][1])
            matrix[i][-1] += min(matrix[i-1][-2], matrix[i-1][-1])
            j = 1
            while j < n-1:
                matrix[i][j] += min(matrix[i-1][j-1], matrix[i-1][j], matrix[i-1][j+1])
                j += 1
            i += 1
        return min(matrix[n-1])

if __name__ == '__main__':
    print(Solution().minFallingPathSum([[-19,57],[-40,-5]]))
